Rational Root Lemma

Using the divisor counting function, this narrows down the number of possible rational roots to check to at most $2d(a_0)d(a_n)$ where the $2$ comes from both positive and negative cases. Because of this, any common factor of the coefficients should be removed to reduce the number of possible cases to check.

Similarly, any rational polynomial can have it's denominators cleared such that the above theorem applies.

Proof

Suppose $\frac{p}{q}$ is a rational root of $f$ with $gcd(p,q)=1$. This means that

Multiplying through by $q^n$ leads to an equation

As such, moving $a_n{p}^n$ to the other side and factoring out $q$ we have that

Given that both sides of this equation are integers, we can conclude that $q\mid -a_n{p}^n$ and hence that $q\mid a_n$ by Euclid's lemma and the fact that $gcd(p,q)=1$.

We can also, from (1), move $a_0{q}^n$ to the other side and factor out the $q$ to conclude similarly that $p\mid a_0$.